package com.yun.algorithmproblem.leetcode;

import java.util.HashMap;
import java.util.TreeSet;

/**
 * 1705. 吃苹果的最大数目
 * <p>
 * 有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
 * <p>
 * 你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
 * <p>
 * 给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
 */

/**
 * 方法2:优先级队列,可以多次入队相同天数但是苹果不同的数据,而不是我目前用的方法使用哈希表来维护,将相同天数的苹果相加.
 */
public class Leetcode1705 {

    public static void main(String[] args) {
        Leetcode1705 obj = new Leetcode1705();
        int[] apples = new int[]{1,2,3,5,2};
        int[] days = new int[]{3,2,1,4,2};
        int cnt = obj.eatenApples(apples, days);
        System.out.println(cnt);
    }

    public int eatenApples(int[] apples, int[] days) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int n = apples.length;
        int lastDay = n;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int apple = apples[i];
            if (apple != 0) {
                int day = i + days[i] - 1;
                if (treeSet.contains(day)) {
                    Integer oldApple = hashMap.get(day);
                    hashMap.put(day, oldApple + apple);
                } else {
                    treeSet.add(day);
                    hashMap.put(day, apple);
                }
            }
            while (!treeSet.isEmpty()) {
                Integer oldestDay = treeSet.first();
                if (oldestDay < i) {
                    treeSet.remove(oldestDay);
                    hashMap.remove(oldestDay);
                } else {
                    Integer oldestApple = hashMap.get(oldestDay);
                    cnt++;
                    if (oldestApple == 1) {
                        treeSet.remove(oldestDay);
                        hashMap.remove(oldestDay);
                    } else {
                        hashMap.put(oldestDay, oldestApple - 1);
                    }
                    break;
                }
            }
        }
        while (!treeSet.isEmpty()) {
            Integer oldestDay = treeSet.first();
            Integer oldestApple = hashMap.get(oldestDay);
            int day = oldestDay - lastDay + 1;
            if (day <= oldestApple) {
                cnt+=day;
                lastDay+=day;
            }else {
                cnt+=oldestApple;
            }
            treeSet.remove(oldestDay);
        }
        return cnt;
    }
}
